package com.interview.javabase.algorithm.字符串;

import java.util.Arrays;

/**
 * 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。
 * 例如输入字符串"I am a student. "，则输出"student. a am I"。
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
 *
 * @author zhangshguang
 * @date 2020/10/05
 */
public class 翻转单词顺序 {

    public static void main(String[] args) {
        reverseWords("  hello world!     ");
    }

    public static void reverseWords(String s) {
        char[] chars = s.toCharArray();

        int len = 0;
        int cur = 0;

        // 前一个是空格
        boolean space = true;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                chars[cur++] = chars[i];
                space = false;
            } else if (!space) {
                chars[cur++] = ' ';
                space = true;
            }
        }

        len = space ? (cur - 1) : cur;

        // 先全部翻转
        reverse(chars, 0, len);

        // 提前占位，
        int pre = -1;
        for (int i = 0; i < len; i++) {

            // 为了找到空格的位置
            if (chars[i] != ' ') {
                continue;
            }

            reverse(chars, pre + 1, i);
            pre = i;

        }

        reverse(chars, pre + 1, len);
        System.out.println(new String(chars, 0, len) + "_888");
    }

    private static void reverse(char[] chars, int li, int ri) {
        ri--;
        while (li < ri) {
            char temp = chars[li];
            chars[li] = chars[ri];
            chars[ri] = temp;
            ri--;
            li++;
        }
    }

    private static void reverse(String[] chars, int li, int ri) {
        ri--;
        while (li < ri) {
            String temp = chars[li];
            chars[li] = chars[ri];
            chars[ri] = temp;
            ri--;
            li++;
        }
    }

}
